package dataStructure.linkedList.binaryTree;

import letcode.util.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @Description: 二叉树的先序遍历
 * @Date: 2020/4/22
 * @Author: 许群星
 */
public class PreorderTraversal {
    //先序遍历取值
    ArrayList<Integer> list=new ArrayList<>();

    //递归方法    先父节点，在左节点，在右节点    中，左，右
    public List<Integer> preorder(TreeNode root){
        //为空则返回
        if (root==null)
            return list;
        list.add(root.val);

        if (root.left!=null)
            preorder(root.left);
        if (root.right!=null)
            preorder(root.right);

        return list;
    }

    //迭代    先将右子节点入栈，再将左子节点入栈
    public List<Integer> preorder_diedai(TreeNode root){
        LinkedList<TreeNode> stack=new LinkedList<>();
        LinkedList<Integer> res=new LinkedList<>();
        if (root==null)
            return res;

        stack.add(root);

        while (!stack.isEmpty()){
            TreeNode node=stack.pollLast();
            res.add(node.val);
            if (node.right!=null)
                stack.add(node.right);
            if (node.left!=null)
                stack.add(node.left);
        }
        return res;
    }
}
